package com.itzmn.newcode.offer;


import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/15 16:05
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer， 按照之字打印二叉树，
 *  第一行从左至右，第二行从右至左，第三行从左至右
 *      1
 *    2   3
 *  4  5  6 7
 *8  9 1 1 13
 *   思路：
 *    使用队列存储
 *
 *    当前是奇数行，将数据按照逆序弹出，将子树按照先右再左入队列，
 *    如果是偶数行，将队列数据按照逆序弹出，子树按照从右至左入队列
 */
public class PrintTreeOfShape {

    public static void main(String[] args) {

        new PrintTreeOfShape().init();
    }
    public void init(){

        int[] arrs = {1,2,3,4,5,6};
        TreeNode tree = createTree(arrs);
        Print(tree);
    }

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {



        //当前是奇数行吗
        boolean isoadd = true;

        LinkedList<TreeNode> integers = new LinkedList<>();
        integers.add(pRoot);

        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null){
            return arrayLists;
        }
        while (!integers.isEmpty()){

            //存放上一层的数据，模板
            LinkedList<TreeNode> temp = new LinkedList<>();

            for (int i=0;i<integers.size();i++){
                temp.add(integers.get(i));
            }
            integers.clear();
            ArrayList<Integer> integers1 = new ArrayList<>();
            while (!temp.isEmpty()){
                if (isoadd){
                    TreeNode remove = temp.removeLast();
                    System.out.println(remove.val);
                    integers1.add(remove.val);
                    if (remove.left!=null){
                        integers.add(remove.left);
                    }
                    if (remove.right!=null){
                        integers.add(remove.right);
                    }

                }else {
                    TreeNode remove = temp.removeLast();
                    System.out.println(remove.val);
                    integers1.add(remove.val);
                    if (remove.right!=null){

                        integers.add(remove.right);
                    }
                    if (remove.left!=null){

                        integers.add(remove.left);
                    }
                }
            }
            isoadd = !isoadd;

            arrayLists.add(integers1);
        }
        return arrayLists;


    }

    /**
     * 创建二叉树
     * @param arrs
     * @return
     */
    public TreeNode createTree(int[] arrs){

        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        for (int i:arrs){
            treeNodes.add(new TreeNode(i));
        }
        TreeNode root = treeNodes.get(0);

        for (int i = 0; i < arrs.length/2; i++) {
            if (i*2+1<arrs.length){
                treeNodes.get(i).left=treeNodes.get(i*2+1);
            }
            if(i*2+2<treeNodes.size()){//避免偶数的时候 下标越界
                treeNodes.get(i).right=treeNodes.get(i*2+2);
            }
        }

        return root;

    }


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

}
